A Simple quadratically convergent Interior Point Algorithm for Linear Programming and Convex quadratic Programming

摘要

An algorithm for linear programming (LP) and convex quadratic programming (CQP) is proposed, based on an interior point iteration introduced more than ten years ago by J. Herskovits for the solution of nonlinear programming problems. Herskovits' iteration can be simplified significantly in the LP/CQP case, and quadratic convergence from any initial point can be achieved. Interestingly the resulting algorithm is closely related to a popular scheme, proposed in 1989 by Kojima et al. independently of Herskovits' work.